#define DRIVER 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXCHAR 256
/*
linked list of keyword to search for.
*/
struct kword{
    unsigned char *word;
    struct kword *next;
};

//#define MAXCHAR 256
//max number of states we have room for
static int MaxState;

/*
First level of matching.
Possible value:
(1) EMPTY_SLOT  -2
(2) a character
(3) MULTI_WAY   -1
*/
static int *MatchArray;

#define EMPTY_SLOT -2
#define MULTI_WAY  -1

union GotoTable
{
    int GotoState;
    int *BranchTable;
}static *GotoArrary;

#define FAIL_STATE  -1

static struct kword **OutArrary;

static int *FailArrary;

static int HighState;

static void  AddStateTrans(int ,int ,int);
static void ComputeFail(void);
static void Enter(unsigned char*);
static void FindFail(int ,int ,int);
static void QueueAdd(int* nQueue,int qbeg,int newer);

void MsrchInit(struct kword *klist)
{
    int i;
    struct kword *ktemp;

    //compute maximum number of possible states
    MaxState = 1;
    for (ktemp=klist;ktemp != NULL;ktemp=ktemp->next)
    {
        MaxState += strlen((char*)ktemp->word);
    }

    //allocate memory for arrays
    MatchArray = (int *) malloc(sizeof(int)*MaxState);
    GotoArrary = (union GotoTable *) malloc(sizeof(union GotoTable)*MaxState);
    OutArrary = (struct kword **)malloc(sizeof(struct kword*)*MaxState);
    FailArrary = (int *)malloc(sizeof(int)*MaxState);

    //initialize states array
    for (i=0;i<MaxState;++i)
    {
        MatchArray[i] = EMPTY_SLOT;
        OutArrary[i] = NULL;
    }

    //initialize state_array[0]
    HighState = 0;
    AddStateTrans(0,'a',FAIL_STATE);
    //force  a multiway table
    AddStateTrans(0,'b',FAIL_STATE);

    //step through keywords
    for (;klist != NULL;klist = klist->next)
    {
        Enter(klist->word);
    }

    //setup return to zero transitions for state[0]
    for (i=0;i<MAXCHAR;++i)
    {
        if (GotoArrary[0].BranchTable[i]==FAIL_STATE)
        {
            GotoArrary[0].BranchTable[i]=0;
        }
    }

    //compute failure array
    ComputeFail();
}

/*
add transition from oldState --> NewState for MatchChar
*/
static void AddStateTrans(int oldState,int MatchChar,int NewState)
{
    int i,*temp;
    //is this slot empty ??
    if (MatchArray[oldState] == EMPTY_SLOT)
    {
        MatchArray[oldState]=MatchChar;
        GotoArrary[oldState].GotoState = NewState;
    }
    //is there already a multi-way table ?
    else
    {
        if (MatchArray[oldState]==MULTI_WAY)
        {
            GotoArrary[oldState].BranchTable[MatchChar] = NewState;
        } 
        else
        {//need to convert to multi-way table
            temp = (int*) malloc(sizeof(int)*MAXCHAR);
            for (i=0;i<MAXCHAR;++i)
            {
                temp[i]=FAIL_STATE;
            }
            temp[MatchArray[oldState]] = GotoArrary[oldState].GotoState;
            temp[MatchChar] = NewState;
            MatchArray[oldState] = MULTI_WAY;
            GotoArrary[oldState].BranchTable = temp;
        }
    }
}

/*
add keyword to list of words our machine recognizes
*/
static void Enter(unsigned char *keyword)
{
    int state , k;
    char* save;
    struct kword *ktemp;
    state = 0;
    save =(char*) keyword;

    /*
    first , see whether we can place this word on top of an existing one
    */
    for (;*keyword != '\0';keyword++)
    {
        if (MatchArray[state] == *keyword)
        {
            state = GotoArrary[state].GotoState;
        }
        else
            if (MatchArray[state]==MULTI_WAY)
            {
                if((k=GotoArrary[state].BranchTable[*keyword]) == FAIL_STATE)
                    break;
                else
                    state = k;
            }
            else 
                break;
    }

    //now add new state as needed
    for ( ; *keyword !='\0';keyword++)
    {
        HighState += 1;
        if (HighState >= MaxState)
        {
            fputs("INTERNAL ERROR: too many states\n",stderr);
            exit(EXIT_FAILURE);
        }
        AddStateTrans(state,*keyword,HighState);
        state = HighState;
    }
    // now add this keyword to output list for final state
    ktemp = (struct kword *)malloc(sizeof(struct kword));
    ktemp->word =(unsigned char*) save;
    ktemp->next = OutArrary[state];
    OutArrary[state] = ktemp;

}

/*
    build FailArray and update GotoArray
*/
static void ComputeFail()
{
    int *Queue,qbeg,r,s;
    int i;
    Queue = (int *)malloc(sizeof(int)*MaxState);
    qbeg = 0;
    Queue[0] = 0;

    /*    scan first level and setup initial values for FailArray    */
    for (i=0;i<MAXCHAR;++i)
        if ((s = GotoArrary[0].BranchTable[i])!=0)
        {
            FailArrary[s] =0;
            QueueAdd(Queue,qbeg,s);
        }

        /* now scan lower levels  */
    while(Queue[qbeg] !=0)
    {
        /*   pull off state from front of Queue and advance qbeg */
        r = Queue[qbeg];
        qbeg = r;
        
        //now investigate this state
        if (MatchArray[r] == EMPTY_SLOT)
            continue;
        else
            if (MatchArray[r] == MULTI_WAY)
            {
                for(i=0;i<MAXCHAR;++i)
                    if((s=GotoArrary[r].BranchTable[i]) != FAIL_STATE)
                    {
                        QueueAdd(Queue,qbeg,s);
                        FindFail(FailArrary[r],s,i);
                    }
            }
            else
            {
                QueueAdd(Queue,qbeg,GotoArrary[r].GotoState);
                FindFail(FailArrary[r],GotoArrary[r].GotoState,MatchArray[r]);
            }
    }
    free(Queue);
}

/*--------------------------------------------------------
*Actually compute failure transition. We know that 'a'
*would normally cause us to go from state s1 to s2.
*To compute the faulure value, we backtrack in search
* of other places 'a' might go.
*---------------------------------------------------------
*/
static void FindFail(int s1, int s2,int a)
{
    int on_fail;
    struct kword *ktemp,kdummy,*out_copy,*kscan;
    for (;;s1= FailArrary[s1])
        if(MatchArray[s1]==a)
        {
            if((on_fail = GotoArrary[s1].GotoState) != FAIL_STATE)
                break;
        }
        else
            if(MatchArray[s1] != EMPTY_SLOT)
                if((on_fail = GotoArrary[s1].BranchTable[a]) != FAIL_STATE)
                    break;
    FailArrary[s2] = on_fail;

    if(OutArrary[on_fail]==NULL)
        out_copy = NULL;
    else
    {
        kscan = OutArrary[on_fail];
        out_copy = (struct kword*)malloc(sizeof(struct kword));
        out_copy->word = kscan->word;
        out_copy->next = NULL;
        for (kscan=kscan->next;kscan!=NULL;kscan = kscan->next)
        {
            ktemp = (struct kword*)malloc(sizeof(struct kword));
            ktemp->word = kscan->word;
            ktemp->next = out_copy->next;
            out_copy->next = ktemp;
        }
    }
    if ((kdummy.next=OutArrary[s2])!=NULL)
    {
        ktemp = &kdummy;
        for(;ktemp->next->next != NULL;ktemp = kdummy.next)
            ;
        ktemp->next->next = out_copy;
    }
    else
        OutArrary[s2] = out_copy;
}

/************************************************************************/
/* add newer to the end of Queue                                        */
/************************************************************************/

static void QueueAdd(int* nQueue,int qbeg,int newer)
{
    int q;
    q = nQueue[qbeg];
    if(q==0)
        nQueue[qbeg] = newer;
    else
    {
        for(;nQueue[q]!=0;q= nQueue[q])
            ;
        nQueue[q] = newer;
    }
    nQueue[newer] = 0;
}

/************************************************************************/
/* do the actual search                                                 */
/************************************************************************/
void MsrchGo(int (*MsrchData)(),void (*MsrchSignal)(char *))
{
    int state,c,g,m;
    struct kword *kscan;
    state = 0;
    while((c=MsrchData())!=EOF)
    {
        for(;;)
        {
            /************************************************************************/
            /* we cheat slightly in the interest of speed/simplicity.The machine will*/
            /* spend most of its time in state==0 , and this state is always a MULTI_WAY */
            /* table .Since this is a simple test , we make it first and try to save the */
            /* calcalation of an array index                                          */
            /************************************************************************/
            if(state==0 || (m = MatchArray[state])==MULTI_WAY)
                g = GotoArrary[state].BranchTable[c];
            else
            {
                if(m==c)
                    g = GotoArrary[state].GotoState;
                else
                    g = FAIL_STATE;
            }

            if(g != FAIL_STATE)
                break;

            state = FailArrary[state];
        }
        state = g;

        if((kscan = OutArrary[state])!=NULL)
            for(;kscan!=NULL;kscan=kscan->next)
                MsrchSignal((char*)kscan->word);
    }
}


/************************************************************************/
/* At the end of program , we should free the memory we malloc.         */
/************************************************************************/
void MsrchEnd()
{
    int i;
    struct kword *kscan;
    for(i=0;i<MaxState;++i)
        if(MatchArray[i]==MULTI_WAY)
            free(GotoArrary[i].BranchTable);

    free(MatchArray);
    free(GotoArrary);
    free(FailArrary);

    for (i=0;i<MaxState;++i)
        if(OutArrary[i]!=NULL)
            for(kscan=OutArrary[i];kscan!=NULL;kscan=kscan->next)
                free(kscan);
    free(OutArrary);
}

#ifdef DRIVER
#define BUFSIZE	200


FILE *infile;
char inbuf[BUFSIZE];
char *inbufptr;
int linecount;

int RetrieveChar(void);
void FoundWord(char *);

int mainf(int argc, char **argv){
	// argc = 4;
	/*strcpy(argv[1], "t.txt");
	strcpy(argv[2], "\0");
	strcpy(argv[3], "%s");*/
	// argv = {"Test.exe", "t.txt", "\0", "%s"};
	char infile_name[80];
	// system("Test.exe t.txt \0 %s");
	struct kword *khead, *ktemp;
	int i;
	if(argc < 3){
		fprintf(stderr, "Usage: msrch infile word-1 word-2....word-n\n");
		exit(EXIT_FAILURE);
	}
	strcpy(infile_name, argv[1]);
	if((infile = fopen(infile_name, "r")) == NULL){
		fprintf(stderr, "Cannot open file %s\n", infile_name);
		exit(EXIT_FAILURE);
	}
	linecount = 0; inbufptr = NULL;

	khead = NULL;
	for(i = 3; i <= argc; i++){
		ktemp = (struct kword *)malloc(sizeof(struct kword));
		ktemp->word = (unsigned char *)argv[i - 1]; // char* cannot be assigned to an entity of type unsigned char*
		ktemp->next = khead;
		khead = ktemp;
	}

	MsrchInit(khead);
	MsrchGo(RetrieveChar, FoundWord);
	MsrchEnd();

	return (EXIT_SUCCESS);
}

int RetrieveChar(void){
	int c;
	if(inbufptr == NULL || *(++inbufptr) == '\0'){
		if(fgets(inbuf, BUFSIZE, infile) == NULL){
			fclose(infile);
			return EOF;
		}
		inbufptr = inbuf;
		linecount += 1;
	}
	c = *inbufptr;
	c &= 0x00FF;
	return c;
}

void FoundWord(char *word){
	int i;
	fprintf(stdout, "Line %d\n%s", linecount, inbuf);
	i = (inbufptr - inbuf) - strlen(word) + 1;
	for(; i > 0; i --){
		fputc(' ', stdout);
	}
	fprintf(stdout, "%s\n\n", word);
}
#endif